using NUnit.Framework;

namespace Solver
{
	/// <summary>
	/// Find the longest sequence using a starting number under one million.
	/// </summary>
	public class Problem014 : SelfChecker, IProblem
	{
		public int Id
		{
			get { return 14; }
		}

		public string Solve()
		{
			return Solve(1000000).ToString();
		}

		[Test]
		public override void Check()
		{
			Assert.AreEqual(9, Solve(10));
			Assert.AreEqual(97, Solve(100));
			Assert.AreEqual(871, Solve(1000));
			Assert.AreEqual(837799, Solve(1000000));
		}

		private static long Solve(int param)
		{
			var lengths = new long[3 * param + 2];
			lengths[1] = 1;
			long result = 1;
			long maxLen = 1;
			for (int i = 2; i < param; i++)
			{
				if (lengths[i] != 0) continue;
				long prev = i;
				var next = Next(i);
				var nextLength = lengths[next];
				while (nextLength == 0)
				{
					lengths[next] = prev;
					prev = next;
					next = Next(prev);
					nextLength = next < lengths.Length ? lengths[next] : BruteForce(next, lengths);
				}
				while (lengths[prev] != 0)
				{
					var tmp = lengths[prev];
					lengths[prev] = ++nextLength;
					prev = tmp;
				}
				Assert.AreEqual(i, prev);
				lengths[i] = nextLength + 1;
				if (lengths[i] > maxLen)
				{
					result = i;
					maxLen = lengths[i];
				}
			}
			return result;
		}

		private static long BruteForce(long n, long[] lengths)
		{
			long tail = 1;
			while (n >= lengths.Length || lengths[n] == 0)
			{
				tail++;
				n = Next(n);
			}
			return tail + lengths[n];
		}

		private static long Next(long n)
		{
			return n % 2 == 0 ? n / 2 : 3 * n + 1;
		}
	}
}